Programmable logic devices (PLDs) are integrated circuits (ICs) that are used to implement digital logic operations according to user configurable input. Example PLDs include Complex Programmable Logic Devices (CPLDs) and field programmable gate arrays (FPGAs). CPLDs often include several function blocks that are based on programmable logic array (PLA) architecture with sum-of-products logic. A configurable interconnect matrix transmits signals between the function blocks.
An example FPGA includes an array of configurable logic blocks (CLBs) and a ring or columns of programmable input/output blocks (IOBs). The CLBs and IOBs are interconnected by a programmable interconnect structure (routing resources). The CLBs, IOBs, and interconnect structure are typically programmed by loading a stream of configuration data (bitstream) into internal configuration memory cells that define how the CLBs, IOBs, and interconnect structure are configured. The configuration bitstream may be read from an external memory, conventionally an external integrated circuit memory EEPROM, EPROM, PROM, and the like, though other types of memory may be used. The collective states of the individual memory cells determine the function of the FPGA. A specific type of FPGA uses a look-up-table (LUT)-based CLB. The configuration memory provides input values to a number of multiplexers controlled by inputs to the CLB.
A conventional design process for an integrated circuit, such as an ASIC or an FPGA begins with the creation of the design. The design specifies the function of a circuit design at a schematic or logic level and may be represented using various programmable languages (e.g., VHDL, ABEL or Verilog) or schematic capture programs. The design is synthesized to produce a logical network list (“netlist”) supported by the target integrated circuit device. The synthesized design is mapped onto primitive components within the target device (e.g., programmable logic blocks of an FPGA).
Following mapping, placement of the components of the synthesized and mapped design is then performed for the target device. During placement, each mapped component of the design is assigned to a physical position on the chip. The purpose of the placer is to place connected design objects in close physical proximity to one another. This conserves space on the chip and increases the probability that the desired interconnections between components will be successfully completed by the router. Placing connected components close to one another also generally improves the performance of the circuit, since long interconnect paths are associated with excess capacitance and resistance, resulting in longer delays.
Specified connections between components of the design are routed within the target device for the placed components. Routing specifies physical wiring resources that will be used to conduct signals between pins of placed components of the design. For each connection specified in the design, routing must allocate wiring necessary to complete the connection. As used herein, the selection and assignment of wire resources in connecting the output pin of one component to the input pin of another component is referred to as routing a signal. When signals have been routed using most or all of the wiring resources in a given area, the area is generally referred to as congested, which creates competition for the remaining wiring resources in the area or makes routing of additional signals in the area impossible.
Place-and-route procedures sometimes involve optimizations of a design's timing, power consumption, routing resources utilized, and any combination thereof. In some instances, timing-based estimations of the design are also provided.
The circuit design process generally includes functional and timing simulations to verify correct operation prior to manufacturing. A design may be modified several times to correct errors identified during testing. Whenever a modification is made, the design place-and-route procedures must be repeated. Due to the large amount of time required for placement and routing of an entire design, it is desirable to avoid repeating the entire place-and-route process when only a small portion of the design has changed.
One solution is to perform place-and-route with criteria to preserve placed and routed portions of the design which are not changed. This is known as incremental placement and routing. However, due to congestion, it may not be possible to route modified signals of the design without rerouting some signals of the unchanged portion of the design. Routing software may waste a large amount of processing trying to avoid rerouting when preservation of the entire unchanged portion is not possible.
The present invention may address one or more of the above issues.